package com.le.enhance.class6;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * 环形单链表的约瑟夫问题
 * 输入：一个环形单向链表的头节点head和报数的值m。
 * 返回：最后生存下来的节点，且这个节点自己组成环形单向链表，其他节点都 删掉。
 * 进阶： 如果链表节点数为N，想在时间复杂度为O(N)时完成原问题的要求，该怎么实现？
 */
public class Code_06_JosephusProblem {
    public static class Node {
        int value;
        Node next;

        public Node(int value) {
            this.value = value;
        }
    }

    // 时间复杂度O(n * logn)
    public static Node process(Node head, int m) {
        if (head == null || m < 1 || head.next == head) {
            return head;
        }
        Node temp = head;
        while (temp.next != head) {
            temp = temp.next;
        }
        int count = 0;
        while (temp != head) {
            if (++count == m) {
                temp.next = head.next;
                count = 0;
            } else {
                temp = temp.next;
            }
            head = temp.next;
        }
        return head;
    }

    // 时间复杂度为O(N)
    public static Node process2(Node head, int m) {
        if (head == null || m < 1 || head.next == head) {
            return head;
        }
        int length = 1;
        Node temp = head.next;
        while (temp != head) {
            length++;
            temp = temp.next;
        }
        length = getLive(length, m);
        while (--length != 0) {
            head = head.next;
        }
        head.next = head;
        return head;
    }

    // 旧编号 = (新编号 - 1 + s) % i + 1
    // s = (m - 1) % i + 1
    // ==> 旧编号 = (新编号 + m - 1) % i + 1
    /**
     * 返回结点新编号
     * @param i 长度
     * @param m 第几个人杀死
     * @return
     */
    public static int getLive(int i, int m) {
        if (i == 1) {
            return 1;
        }
        return (getLive(i - 1, m) + m - 1) % i + 1;
    }

    // list
    public static int testForList(int m) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < 5; i++) {
            list.add(i + 1);
        }
        int index = 0;
        int count = 1;
        while (list.size() != 1) {
            if (++count == m) {
                list.remove(index);
                count = 0;
            }
            index = (index + 1) % list.size();
        }
        return list.get(0);
    }

    @Test
    public void test() {
        Node head1 = new Node(1);
        head1.next = new Node(2);
        head1.next.next = new Node(3);
        head1.next.next.next = new Node(4);
        head1.next.next.next.next = new Node(5);
        head1.next.next.next.next.next = head1;
//        System.out.println(process(head1, 3).value);
//        System.out.println(process2(3));
        System.out.println(process2(head1, 3).value);
    }


}
